
import math
import sys
from random import shuffle

class HeapPrintTree_CLS(object):

	def __init__(self, listIn):
		super(HeapPrintTree_CLS, self).__init__()
		self.theHeap = []
		self.listInToPrint = listIn;
		self.itemsInArray = 0;
		self.maxSize = len(self.listInToPrint);
		self.filleArray()
	

	def insert(self, index, newData):
		self.theHeap.append(newData)
		self.itemsInArray += 1
	

	def calculateRows(self, listIn):
		listSize = len(listIn)
		maxPowValue = 1
		intRows = 1

		while (listSize/maxPowValue) >= 1:
		
			maxPowValue += math.pow(2, intRows)

			intRows += 1

		return intRows
	

	def printTree(self):
		rows = self.calculateRows(self.listInToPrint)
		spaces = 0
		iteration = 1
		indent = self.getIndentArray(rows)

		while (iteration <= rows):
			indexToPrint = int(.5 * (-2 + (math.pow(2, iteration))))
			itemsPerRow = int(math.pow(2, iteration - 1))
			maxIndexToPrint = indexToPrint + itemsPerRow

			for j in range(0, indent[iteration - 1], 1):
				sys.stdout.write(' ')
			for l in range(indexToPrint, maxIndexToPrint, 1):
				if l < self.itemsInArray:
					sys.stdout.write('{0} '.format(self.theHeap[l].key))
					for k in xrange(0, spaces,1):
						sys.stdout.write(' ')			

			spaces = indent[iteration - 1]
			iteration += 1
			print
			sys.stdout.flush()

	def getIndentArray(self, rows):
		indentArray = []

		for i in xrange(0, rows):
			indentArray.append(int(math.fabs((-2 + (math.pow(2, i + 1))))))

		indentArray = self.reverseArray(indentArray)
		return indentArray
	
	
	def reverseArray(self, theArray):
		leftIndex = 0
		rightIndex = len(theArray) - 1

		while (leftIndex < rightIndex):
			theArray[leftIndex], theArray[rightIndex] = theArray[rightIndex], theArray[leftIndex]
			leftIndex += 1
			rightIndex -= 1
		
		return theArray
	

	def filleArray(self):
		randomData1 = Data3

		for i in xrange(0, self.maxSize):
			randomData1 = Data3(self.listInToPrint[i])
			self.insert(i, randomData1)
		
	


class Data3(object):

	def __init__(self, key):
		super(Data3, self).__init__()
		self.key = key;
	



"""
if __name__ == "__main__":
	lista=[]
	for i in xrange(1, 13):
		lista.append(i)
	#lista=[16,4,10,14,7,9,3,2,1,8]
	shuffle(lista)

	heapObject = HeapPrintTree_CLS(lista)
	heapObject.printTree()
"""